package zuoshen_mid.class1.skill1;
import java.util.*;

import org.junit.Test;
public class RipeToOverPoints {
    
    //一个数组，一个L长的绳子，试图去覆盖尽量多的数轴的点（这些存在的点都记录在nums[有序数组]中）
    public int numberOfOver(int[] nums, int l) {
        /*  
            每次到达一个点，都去查看左边能够覆盖多少点
        */

        int cur = 0, res = 1;
        Deque<Integer> deque = new LinkedList<>();
        int idx = 0;
        while (cur <= l) {
            deque.offerLast(idx);
            idx++;
            cur += (nums[idx] - nums[idx-1]);
        }
        res = deque.size();
        deque.offerLast(idx);
        while (cur > l) {
            int p = deque.pollFirst();
            cur -= (nums[deque.peekFirst()] - nums[p]);
        }
        for (int i = idx + 1; i < nums.length; i++) {
            deque.offerLast(i);
            cur += (nums[i] - nums[i - 1]);
            while (cur > l) {
                int p = deque.pollFirst();
                cur -= (nums[deque.peekFirst()] - nums[p]);
            }
            res = Math.max(res, deque.size());
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = {2, 4, 8, 9};
        System.out.println(numberOfOver(nums, 5));
    }
}
